package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.corba.se.impl.orbutil.graph.Node;
import com.sun.javafx.image.IntPixelAccessor;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.datastructure.ListNode;

/*
 * 
 原题　
	 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
	
	 The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
	
	 How many possible unique paths are there?
	
	
	 Above is a 3 x 7 grid. How many possible unique paths are there?
	
	 Note: m and n will be at most 100.
 题目大意

 解题思路
	TODO:尚未测试
 @Type 动态规划
 * @Date 2017-09-22 01:38
 */
public class _068_Unique_Paths {

	public int uniquePaths(int m, int n) {
		//动态规划
		int[][] dp = new int[m][n];
		
		for (int i = 0; i < m; i ++) {
			//eg：因为机器人只能下或者右走，因此要想走到 [3][0],只有一条路线：即一直下走
			dp[i][0] = 1;				
		}
		
		for (int j = 0; j < n; n ++) {
			
			dp[0][j] = 1;				
		}
		
		for (int i = 1; i < m; i ++) {
			for (int j = 1; j < n; j ++) {
				dp[i][j] = dp[i-1][j] + dp[i][j-1];
			}
		}
		return dp[m-1][n-1];
	}

	public static void main(String[] args) {
		_068_Unique_Paths obj = new _068_Unique_Paths();

		ListNode list = ListNode.newLinkList2();
		obj.uniquePaths(3, 7);

		// ListNode.traverse("remove", list);
	}

}
